import java.util.Arrays;

/**
 * 321. 拼接最大数
 * https://leetcode-cn.com/problems/create-maximum-number/
 */
public class Solutions_321 {
    public static void main(String[] args) {
//        int[] nums1 = {3, 4, 6, 5}, nums2 = {9, 1, 2, 5, 8, 3};
//        int k = 5;  // output: {9, 8, 6, 5, 3}

//        int[] nums1 = {7, 6, 1, 9, 3, 2, 3, 1, 1}, nums2 = {4, 0, 9, 9, 0, 5, 5, 4, 7};
//        int k = 9;  // output: {9, 9, 9, 7, 3, 2, 3, 1, 1}

//        int[] nums1 = {6, 7}, nums2 = {6, 0, 4};
//        int k = 5;  // output: {6, 7, 6, 0, 4}

//        int[] nums1 = {3, 9}, nums2 = {8, 9};
//        int k = 3;  // output: {9, 8, 9}

//        int[] nums1 = {6, 7, 5}, nums2 = {4, 8, 1};
//        int k = 3;  // output: {8, 7, 5}

        int[] nums1 = {2, 5, 6, 4, 4, 0}, nums2 = {7, 3, 8, 0, 6, 5, 7, 6, 2};
        int k = 15;  // output: {7, 3, 8, 2, 5, 6, 4, 4, 0, 6, 5, 7, 6, 2, 0}


        int[] result = maxNumber(nums1, nums2, k);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解题思路：
     * 1. 从 nums1 数组和 nums2 数组中取出 k 个相对排列的元素，保证组成的数字最大
     * 2. 尝试从 nums1 中取 [0, k] 个最大组合，再尝试从 nums2 中取 [0, k - i] 个最大组合
     *      子序列取值 关键：单调栈实现（栈中元素，单调递减），定义 delCnt 变量，记录可以在单调栈中移除元素的数量
     * 3. 将两个最大组合合并成一个长度为 k 的最大组合
     *      合并 关键：两个值相等时，还需要判断后面的元素，才能保证组合的数值最大
     * 4. 将一轮得到的最大组合，与 res 比较，保留最大的组合
     */
    public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] res = new int[k];
        int len1 = nums1.length, len2 = nums2.length;
        // 从 nums1 中选出长度为 i 的最大子序列，i 必须小于等于 k
        for (int i = 0; i <= k && i <= len1; i++) {
            // k - i 数量必须合法，最多从 nums2 中取 len2 个，最少取 0 个
            if (k - i >= 0 && k - i <= len2) {
                // 从 nums2 中选出长度为 k - i 的最大子序列
                int[] sub1 = getSubMax(nums1, i);
                int[] sub2 = getSubMax(nums2, k - i);
                // 合并，返回能够组成的最大数
                int[] mergeArr = merge(sub1, sub2);
                // 比较，若 mergeArr 大于 res，则替换结果
                if (max(mergeArr, res)) {
                    res = mergeArr;
                }
            }
        }
        return res;
    }

    /**
     * 在 nums 中返回长度为 len 的最大子序列
     */
    public static int[] getSubMax(int[] nums, int len) {
        // 在 cur 中可删除元素的数量
        int delCnt = nums.length - len;
        int[] cur = new int[len];
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            // 维护一个单调递减的数组
            while (delCnt > 0 && idx > 0 && nums[i] > cur[idx - 1]) {
                idx --;
                // 可删除数量减 1
                delCnt --;
            }
            if (idx < len) {
                // 栈中还可以添加元素，那么继续添加
                cur[idx ++] = nums[i];
            } else {
                // 关键：该元素未添加到栈中，那么 delCnt 也相应减 1
                delCnt --;
            }
        }
        return cur;
    }

    /**
     * 合并两个数组，元素按降序排列
     */
    public static int[] merge(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int[] cur = new int[len1 + len2];
        int idx = 0, i = 0, j = 0;
        while (idx < cur.length) {
            // 例：int[] nums1 = {2, 5, 6, 4, 4, 0}, nums2 = {7, 3, 8, 0, 6, 5, 7, 6, 2};
            // int k = 15;  // output: {7, 3, 8, 2, 5, 6, 4, 4, 0, 6, 5, 7, 6, 2, 0}
            // 以上情况，两个 0 相等时，还需要判断后面的元素
            // 否则是错误结果：{7, 3, 8, 2, 5, 6, 4, 4, 0, 0, 6, 5, 7, 6, 2}
            // a == b 时，取值规则：
            // 1. a 后面还有元素，b 后面没有元素了，那么取 a
            // 2. a 后面还有元素，b 后面还有元素，那么继续判断后一元素
            if (compare(nums1, i, nums2, j)) {
                cur[idx] = nums1[i ++];
            } else {
                cur[idx] = nums2[j ++];
            }
            idx ++;
        }
        return cur;
    }

    /**
     * 递归实现比较
     * a == b 时，取值规则：
     * 1. a 后面还有元素，b 后面没有元素了，那么取 a
     * 2. a 后面还有元素，b 后面还有元素，那么继续判断后一元素
     */
    public static boolean compare(int[] nums1, int i, int[] nums2, int j) {
        if (i == nums1.length) {
            return false;
        } else if (j == nums2.length) {
            return true;
        } else if (nums1[i] > nums2[j]) {
            return true;
        } else if (nums1[i] < nums2[j]) {
            return false;
        }
        // 当前索引上的两元素相等，那么判断下一索引
        return compare(nums1, i + 1, nums2, j + 1);
    }

    /**
     * 比较两个数组组成的数
     * @return cur 组成的数是否大于 res 组成的数
     */
    public static boolean max(int[] cur, int[] res) {
        for (int i = 0; i < cur.length; i++) {
            if (cur[i] < res[i]) {
                return false;
            } else if (cur[i] > res[i]) {
                return true;
            }
        }
        return true;
    }
}
